// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package strconv

// 十进制到二进制浮点转换。
// 算法：
// 1）以多精度十进制存储输入。
// 2）将十进制数乘以/除以二的幂，直到在范围内[0.5,1）
// 3）乘以2^精度并取整得到尾数。

import "math"

var optimize = true // 设置为false可强制进行慢路径转换以测试

// CommonPrefixEngNorecase返回通用
// 前缀s和前缀的长度，忽略字符大小写。
// 前缀参数必须全部为小写。
func commonPrefixLenIgnoreCase(s, prefix string) int {
	n := len(prefix)
	if n > len(s) {
		n = len(s)
	}
	for i := 0; i < n; i++ {
		c := s[i]
		if 'A' <= c && c <= 'Z' {
			c += 'a' - 'A'
		}
		if c != prefix[i] {
			return i
		}
	}
	return n
}

// special返回特殊的浮点值，
// 可能有符号的浮点表示形式inf、infinity、
// 和NaN。如果s的前缀包含这些表示形式中的一个
// 且n是该前缀的长度，则结果是确定的。
// 忽略字符大小写。
func special(s string) (f float64, n int, ok bool) {
	if len(s) == 0 {
		return 0, 0, false
	}
	sign := 1
	nsign := 0
	switch s[0] {
	case '+', '-':
		if s[0] == '-' {
			sign = -1
		}
		nsign = 1
		s = s[1:]
		fallthrough
	case 'i', 'I':
		n := commonPrefixLenIgnoreCase(s, "infinity")
		// 任何长度超过“inf”的都可以，但是如果我们没有“无穷大”，只使用“inf”.
		if 3 < n && n < 8 {
			n = 3
		}
		if n == 3 || n == 8 {
			return math.Inf(sign), nsign + n, true
		}
	case 'n', 'N':
		if commonPrefixLenIgnoreCase(s, "nan") == 3 {
			return math.NaN(), 3, true
		}
	}
	return 0, 0, false
}

func (b *decimal) set(s string) (ok bool) {
	i := 0
	b.neg = false
	b.trunc = false

	// 可选符号
	if i >= len(s) {
		return
	}
	switch {
	case s[i] == '+':
		i++
	case s[i] == '-':
		b.neg = true
		i++
	}

	// 数字
	sawdot := false
	sawdigits := false
	for ; i < len(s); i++ {
		switch {
		case s[i] == '_':
			// 已选中的readFloat下划线
			continue
		case s[i] == '.':
			if sawdot {
				return
			}
			sawdot = true
			b.dp = b.nd
			continue

		case '0' <= s[i] && s[i] <= '9':
			sawdigits = true
			if s[i] == '0' && b.nd == 0 { // 忽略前导零
				b.dp--
				continue
			}
			if b.nd < len(b.d) {
				b.d[b.nd] = s[i]
				b.nd++
			} else if s[i] != '0' {
				b.trunc = true
			}
			continue
		}
		break
	}
	if !sawdigits {
		return
	}
	if !sawdot {
		b.dp = b.nd
	}

	// 可选指数移动小数点。
	// 如果我们读取的数字非常大，非常长，
	// 请确保移动小数点p
	// 很多（比如100000）。不管是
	// 不是确切的数字。
	if i < len(s) && lower(s[i]) == 'e' {
		i++
		if i >= len(s) {
			return
		}
		esign := 1
		if s[i] == '+' {
			i++
		} else if s[i] == '-' {
			i++
			esign = -1
		}
		if i >= len(s) || s[i] < '0' || s[i] > '9' {
			return
		}
		e := 0
		for ; i < len(s) && ('0' <= s[i] && s[i] <= '9' || s[i] == '_'); i++ {
			if s[i] == '_' {
				// 已选中的readFloat下划线
				continue
			}
			if e < 10000 {
				e = e*10 + int(s[i]) - '0'
			}
		}
		b.dp += e * esign
	}

	if i != len(s) {
		return
	}

	ok = true
	return
}

// readFloat从浮点读取十进制或十六进制尾数和指数
// 以s表示的字符串；数字后面可能跟有其他字符。
// 读取Float报告消耗的字节数（i），以及数字
// 是否有效（ok）.
func readFloat(s string) (mantissa uint64, exp int, neg, trunc, hex bool, i int, ok bool) {
	underscores := false

	// 可选符号
	if i >= len(s) {
		return
	}
	switch {
	case s[i] == '+':
		i++
	case s[i] == '-':
		neg = true
		i++
	}

	// 数字
	base := uint64(10)
	maxMantDigits := 19 // 10^19适合uint64 
	expChar := byte('e')
	if i+2 < len(s) && s[i] == '0' && lower(s[i+1]) == 'x' {
		base = 16
		maxMantDigits = 16 // 16^16适合uint64 
		i += 2
		expChar = 'p'
		hex = true
	}
	sawdot := false
	sawdigits := false
	nd := 0
	ndMant := 0
	dp := 0
loop:
	for ; i < len(s); i++ {
		switch c := s[i]; true {
		case c == '_':
			underscores = true
			continue

		case c == '.':
			if sawdot {
				break loop
			}
			sawdot = true
			dp = nd
			continue

		case '0' <= c && c <= '9':
			sawdigits = true
			if c == '0' && nd == 0 { // 忽略前导零
				dp--
				continue
			}
			nd++
			if ndMant < maxMantDigits {
				mantissa *= base
				mantissa += uint64(c - '0')
				ndMant++
			} else if c != '0' {
				trunc = true
			}
			continue

		case base == 16 && 'a' <= lower(c) && lower(c) <= 'f':
			sawdigits = true
			nd++
			if ndMant < maxMantDigits {
				mantissa *= 16
				mantissa += uint64(lower(c) - 'a' + 10)
				ndMant++
			} else {
				trunc = true
			}
			continue
		}
		break
	}
	if !sawdigits {
		return
	}
	if !sawdot {
		dp = nd
	}

	if base == 16 {
		dp *= 4
		ndMant *= 4
	}

	// 可选指数移动小数点。
	// 如果我们读取一个非常大、非常长的数字，
	// 只要一定要将小数点移动
	// 很多（比如100000）。如果是
	// 则无所谓。
	if i < len(s) && lower(s[i]) == expChar {
		i++
		if i >= len(s) {
			return
		}
		esign := 1
		if s[i] == '+' {
			i++
		} else if s[i] == '-' {
			i++
			esign = -1
		}
		if i >= len(s) || s[i] < '0' || s[i] > '9' {
			return
		}
		e := 0
		for ; i < len(s) && ('0' <= s[i] && s[i] <= '9' || s[i] == '_'); i++ {
			if s[i] == '_' {
				underscores = true
				continue
			}
			if e < 10000 {
				e = e*10 + int(s[i]) - '0'
			}
		}
		dp += e * esign
	} else if base == 16 {
		// 必须具有指数。
		return
	}

	if mantissa != 0 {
		exp = dp - ndMant
	}

	if underscores && !underscoreOK(s[:i]) {
		return
	}

	ok = true
	return
}

// 十的十进制幂与二的二进制幂之比。
var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26}

func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) {
	var exp int
	var mant uint64

	// 零始终是一个特例。
	if d.nd == 0 {
		mant = 0
		exp = flt.bias
		goto out
	}

	// 明显的溢出/下溢。
	// 这些边界用于64位浮点。
	// 如果我们想在将来支持80位浮点，就必须进行更改。
	if d.dp > 310 {
		goto overflow
	}
	if d.dp < -330 {
		// 零
		mant = 0
		exp = flt.bias
		goto out
	}

	// 按2的幂进行缩放，直到范围[0.5,1.0]
	exp = 0
	for d.dp > 0 {
		var n int
		if d.dp >= len(powtab) {
			n = 27
		} else {
			n = powtab[d.dp]
		}
		d.Shift(-n)
		exp += n
	}
	for d.dp < 0 || d.dp == 0 && d.d[0] < '5' {
		var n int
		if -d.dp >= len(powtab) {
			n = 27
		} else {
			n = powtab[-d.dp]
		}
		d.Shift(n)
		exp -= n
	}

	// 我们的范围是[0.5,1]，但浮点范围是[1,2）.
	exp--

	// 最小可表示指数为flt.bias+1.
	// 如果指数较小，则将其向上移动，并相应地调整d.
	if exp < flt.bias+1 {
		n := flt.bias + 1 - exp
		d.Shift(-n)
		exp += n
	}

	if exp-flt.bias >= 1<<flt.expbits-1 {
		goto overflow
	}

	// 提取1+flt.mantbits位。
	d.Shift(int(1 + flt.mantbits))
	mant = d.RoundedInteger()

	// 舍入可能会增加一位；下移。
	if mant == 2<<flt.mantbits {
		mant >>= 1
		exp++
		if exp-flt.bias >= 1<<flt.expbits-1 {
			goto overflow
		}
	}

	// 非规范化？
	if mant&(1<<flt.mantbits) == 0 {
		exp = flt.bias
	}
	goto out

overflow:
	// /±Inf 
	mant = 0
	exp = 1<<flt.expbits - 1 + flt.bias
	overflow = true

out:
	// 汇编位。
	bits := mant & (uint64(1)<<flt.mantbits - 1)
	bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits
	if d.neg {
		bits |= 1 << flt.mantbits << flt.expbits
	}
	return bits, overflow
}

// 10的精确幂。
var float64pow10 = []float64{
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
	1e20, 1e21, 1e22,
}
var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}

// 如果可以将十进制表示精确地转换为64位浮点f，
// 完全用浮点数学，这样做可以避免以十进制位为代价。
// 三种常见情况：
// 值是精确整数
// 值是精确整数*十个
// 值是精确整数/十个
// 这些都会产生可能不精确但正确的四舍五入答案。
func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) {
	if mantissa>>float64info.mantbits != 0 {
		return
	}
	f = float64(mantissa)
	if neg {
		f = -f
	}
	switch {
	case exp == 0:
		// 一个整数。
		return f, true
	// 精确整数<=10^15。
	// 十的精确幂是<=10^22。
	case exp > 0 && exp <= 15+22: // int*10^k 
		// 如果指数大，但位数不大，
		// 可以将几个零移到整数部分。
		if exp > 22 {
			f *= float64pow10[exp-22]
			exp = 22
		}
		if f > 1e15 || f < -1e15 {
			// 指数实在太大了。
			return
		}
		return f * float64pow10[exp], true
	case exp < 0 && exp >= -22: // int/10^k 
		return f / float64pow10[-exp], true
	}
	return
}

// 如果可能的话，可以计算尾数*10^exp精确到32位浮点f，
// 完全在浮点数学中，这样做，避免上面的机械。
func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) {
	if mantissa>>float32info.mantbits != 0 {
		return
	}
	f = float32(mantissa)
	if neg {
		f = -f
	}
	switch {
	case exp == 0:
		return f, true
	// 精确整数是<=10^7。
	// 十的精确幂是<=10^10。
	case exp > 0 && exp <= 7+10: // int*10^k 
		// 如果指数大，但位数不是，
		if exp > 10 {
			f *= float32pow10[exp-10]
			exp = 10
		}
		if f > 1e7 || f < -1e7 {
			// 指数太大。
			return
		}
		return f * float32pow10[exp], true
	case exp < 0 && exp >= -10: // int/10^k 
		return f / float32pow10[-exp], true
	}
	return
}

// atofHex将十六进制浮点字符串s 
// 转换为舍入的float32或float64值（取决于flt==&float32info或flt=&float64info）
// 并将其作为float64返回。
// 字符串s已被解析为尾数、指数和符号（负=true）。
// 如果trunc为true，尾数中的尾随非零位已被忽略。
func atofHex(s string, flt *floatInfo, mantissa uint64, exp int, neg, trunc bool) (float64, error) {
	maxExp := 1<<flt.expbits + flt.bias - 2
	minExp := flt.bias + 1
	exp += int(flt.mantbits) // 尾数现在隐式除以2^尾数。

	// 移动尾数和指数，将表示带入浮点范围。
	// 最终我们需要一个尾数，尾数的前导是1位，后面是尾数位和其他位。
	// 对于舍入，我们还需要两个，其中底部的位表示
	// 该位或任何后续位是否为非零。
	// （如果尾数已经丢失了非零位，trunc为真，
	// ，适当向左移位后，我们或在下面的a 1中。）
	for mantissa != 0 && mantissa>>(flt.mantbits+2) == 0 {
		mantissa <<= 1
		exp--
	}
	if trunc {
		mantissa |= 1
	}
	for mantissa>>(1+flt.mantbits+2) != 0 {
		mantissa = mantissa>>1 | mantissa&1
		exp++
	}

	// 如果指数太负，
	// 反规范化，希望使其具有代表性。
	// （2表示舍入位。）
	for mantissa > 1 && exp < minExp-2 {
		mantissa = mantissa>>1 | mantissa&1
		exp++
	}

	// 使用两个底部位进行舍入。
	round := mantissa & 3
	mantissa >>= 2
	round |= mantissa & 1 // 四舍五入到偶数（尾数为奇数时四舍五入）
	exp += 2
	if round == 3 {
		mantissa++
		if mantissa == 1<<(1+flt.mantbits) {
			mantissa >>= 1
			exp++
		}
	}

	if mantissa>>flt.mantbits == 0 { // 非规范或零。
		exp = flt.bias
	}
	var err error
	if exp > maxExp { // 无穷大和范围错误
		mantissa = 1 << flt.mantbits
		exp = maxExp + 1
		err = rangeError(fnParseFloat, s)
	}

	bits := mantissa & (1<<flt.mantbits - 1)
	bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits
	if neg {
		bits |= 1 << flt.mantbits << flt.expbits
	}
	if flt == &float32info {
		return float64(math.Float32frombits(uint32(bits))), err
	}
	return math.Float64frombits(bits), err
}

const fnParseFloat = "ParseFloat"

func atof32(s string) (f float32, n int, err error) {
	if val, n, ok := special(s); ok {
		return float32(val), n, nil
	}

	mantissa, exp, neg, trunc, hex, n, ok := readFloat(s)
	if !ok {
		return 0, n, syntaxError(fnParseFloat, s)
	}

	if hex {
		f, err := atofHex(s[:n], &float32info, mantissa, exp, neg, trunc)
		return float32(f), n, err
	}

	if optimize {
		// 尝试纯浮点算术转换，如果失败，
		// 使用Eisel-Lemire算法。
		if !trunc {
			if f, ok := atof32exact(mantissa, exp, neg); ok {
				return f, n, nil
			}
		}
		f, ok := eiselLemire32(mantissa, exp, neg)
		if ok {
			if !trunc {
				return f, n, nil
			}
			// 即使尾数被截断，我们也可能找到了正确的结果。通过
			// 转换尾数上限进行确认。
			fUp, ok := eiselLemire32(mantissa+1, exp, neg)
			if ok && f == fUp {
				return f, n, nil
			}
		}
	}

	// 缓慢回退。
	var d decimal
	if !d.set(s[:n]) {
		return 0, n, syntaxError(fnParseFloat, s)
	}
	b, ovf := d.floatBits(&float32info)
	f = math.Float32frombits(uint32(b))
	if ovf {
		err = rangeError(fnParseFloat, s)
	}
	return f, n, err
}

func atof64(s string) (f float64, n int, err error) {
	if val, n, ok := special(s); ok {
		return val, n, nil
	}

	mantissa, exp, neg, trunc, hex, n, ok := readFloat(s)
	if !ok {
		return 0, n, syntaxError(fnParseFloat, s)
	}

	if hex {
		f, err := atofHex(s[:n], &float64info, mantissa, exp, neg, trunc)
		return f, n, err
	}

	if optimize {
		// 尝试纯浮点算术转换，如果失败，则使用Eisel-Lemire算法。
		if !trunc {
			if f, ok := atof64exact(mantissa, exp, neg); ok {
				return f, n, nil
			}
		}
		f, ok := eiselLemire64(mantissa, exp, neg)
		if ok {
			if !trunc {
				return f, n, nil
			}
			// 即使尾数被截断，我们也可能找到了正确的结果。通过
			// 转换尾数上限进行确认。
			fUp, ok := eiselLemire64(mantissa+1, exp, neg)
			if ok && f == fUp {
				return f, n, nil
			}
		}
	}

	// 缓慢后退。
	var d decimal
	if !d.set(s[:n]) {
		return 0, n, syntaxError(fnParseFloat, s)
	}
	b, ovf := d.floatBits(&float64info)
	f = math.Float64frombits(b)
	if ovf {
		err = rangeError(fnParseFloat, s)
	}
	return f, n, err
}

// ParseFloat将字符串s转换为浮点数
// 精度由位大小指定：32表示float32，64表示float64。
// 当bitSize=32时，结果的类型仍然是float64，但它将是
// 可转换为float32而不更改其值。
// 
// ParseFloat接受十进制和十六进制浮点数语法。
// 如果s格式正确且接近有效的浮点数，
// ParseFloat将使用IEEE754无偏舍入返回最接近的四舍五入浮点数
// 。
// （只有在
// 十六进制表示中的位数多于尾数中的
// 时，才对十六进制浮点值进行舍入分析。）
// 
// ParseFloat返回的错误具有具体类型*numeror 
// 并包含err.Num=s。
// 
// 如果s的语法格式不正确，则ParseFloat返回err.err=ErrSyntax。
// 
// 如果s在语法上格式正确，但与给定大小的最大浮点数的距离超过1/2 ULP 
// 则
// ParseFloat返回f=±Inf，err.err=ErrRange。
// 
// ParseFloat将字符串“NaN”以及（可能有符号的）字符串“Inf”和“Infinity”识别为各自的特殊浮点值。匹配时忽略大小写。
func ParseFloat(s string, bitSize int) (float64, error) {
	f, n, err := parseFloatPrefix(s, bitSize)
	if n != len(s) && (err == nil || err.(*NumError).Err != ErrSyntax) {
		return 0, syntaxError(fnParseFloat, s)
	}
	return f, err
}

func parseFloatPrefix(s string, bitSize int) (float64, int, error) {
	if bitSize == 32 {
		f, n, err := atof32(s)
		return float64(f), n, err
	}
	return atof64(s)
}
